NOTES ON AUTOMATA AND ARTIFICIAL INTELLIGENCE


	The reader of these notes is assumed to be familiar with finite
automata and with the idea of a system of interacting finite automata.
It is unlikely that any facts from automata theory per se will be
referred to, because they don't seem to be relevant.

	Our object is to make automata useful for artificial intelligence.
We have several kinds of applications in mind:

	1. The most accessible applications are metaphysical in the sense
of (McCarthy and Hayes 1970).  Namely certain concepts like causality
and ability may be defined for systems of automata and their properties
studied in these systems.  We also want to regard the world as an
inverse limit of a family of systems of automata and "homomorphic" mappings.

	2. There is also some possibility of epistemological use of automata,
i.e. representing actual systems of interest as systems of interacting
automata, but this requires progress in defining ways of presenting automata.


PRESENTATIONS OF AUTOMATA

	For the moment let us fix our attention on finite state automata
with integer time.  In order to describe the automaton, we must give the
functions that give the new state as a function of the previous state and
the input and the output as a function of the state.

	When one is trying
to explain the idea of automaton, there are two common ways of presenting
these functions.  The first is by two tables that list for each input
and state the next state and list the outputs in terms of the states.
The size of the larger table is the product of the number of states and
the number of possible input signals.  In the illustrations given this
product is usually less than 20, and if a computer program were to use
the table for simulating the automaton, the size of the table should
be not more than a few thousand.  The method becomes impractical for
even a calculator even the smallest of which have more than a million
states, since the number of states is exponential in the number of devices.

	The second pedagogical way of presenting automata is with a diagram
representing each state as a circle and each path to another state as
an arc labelled with the inputs that give rise to the transition.  Some
compression is possible if the set of inputs giving rise to a given
transition can be simply presented.  This method is also not practical
for real devices.

	As long as one is discussing the theory of automata or even their
applications to metaphysical questions, there does not have to be a practical
way of presenting them.  If we look at it from the point of view of
mathematical logic, we can write general statements about automata and
develop the theory without having a practical notation for automaton-valued
constants.

	As for a practical notation, here is a simple possibility:  represent
the state of an automaton as an integer and likewise the possible inputs, and
present the functions by any means suitable for presenting functions of
integers, e.g. by formulas built up from arithmetic operations, by
conditional expressions, and finally by programs in some language.
More generally, we can represent the state and input signal as a vector
of integers and represent each component of the new state as a function
of the components of the old state and the input.  Still more generally,
we can use any way of presenting finite objects, e.g. as S-expressions
or as strings and any convenient way of describing functions of such
entities.

	Further elaborations arise if we must present

	(i) Systems of automata with some regular structure, e.g. cellular
arrays of automata.

	(ii) Indeterminate automata in which the next state isn't described
precisely, but only a set from which the next state comes has to be described.
For example, consider the customer in the McCarthy airline reservation system.
At any time he may try to reserve a seat or cancel a reservation, but we
don't want to say which in describing him as an automaton.

	(iii) If we want to simulate a real world phenomenon as a systme of
automata, it may happen that some parts of the system have to be simulated
in more temporal detail than others, i.e. some parts of the system may
change slowly.  Some of the considerations of my note on relativistic
automata apply here. (See McCarthy 1975a).


MAPPINGS OF AUTOMATA